package leetcode;

import java.util.*;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-01-19 00:45
 **/
public class LeetCode220 {
    //桶
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int n = nums.length;
        Map<Long, Long> map = new HashMap<>();
        long bucketSize = t + 1;
        for (int i = 0; i < n; ++i) {
            long id = getId((long) nums[i], bucketSize);
            //如果map中已经存在key为id的元素,说明已经有一个[nums[i] - t, nums[i] + t]的元素了,满足题意,直接返回true
            if (map.containsKey(id)) {
                return true;
            }

            //查看相邻桶中的元素是否满足条件
            if (map.containsKey(id - 1) && Math.abs((long) nums[i] - (long) map.get(id - 1)) <= t) {
                return true;
            }

            if (map.containsKey(id + 1) && Math.abs((long) nums[i] - (long) map.get(id + 1)) <= t) {
                return true;
            }

            //将当前元素添加到map中
            map.put(id, (long) nums[i]);

            //移除左边窗口元素
            if (i >= k) {
                map.remove(getId((long) nums[i - k], bucketSize));
            }
        }

        return false;
    }

    //获取存放的桶的索引
    long getId(long x, long bucketSize) {
        if (x >=0 ) {
            return x / bucketSize;
        }

        return (x + 1) / bucketSize - 1;
    }

    //有序集合+滑动窗口
    /*public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int n = nums.length;
        TreeSet<Long> set = new TreeSet<>();
        for (int i = 0; i < n; i++) {
            //转成long防止溢出
            //找到大于等于(nums[i] - t)的第一个数,找不到为null
            Long ceiling = set.ceiling((long) nums[i] - (long) t);

            //如果ceiling != null 说明存在>= nums[i] - t的数,如果这个数还 <= nums[i] + t的话就满足了题意,直接返回truye
            if (ceiling != null && ceiling <= (long) nums[i] + (long) t) {
                return true;
            }

            set.add((long) nums[i]);
            //如果元素个数达到k个,就溢出最早添加的元素
            if (i >= k) {
                set.remove((long) nums[i - k]);
            }
        }
        return false;
    }*/

}
